import random
from typing import List

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        def get_min_max(arr):
            min_, max_ = 10**10, -10**10
            for x in arr:
                min_ = min(min_, x)
                max_ = max(max_, x)
            return min_, max_
        min_, max_ = get_min_max(nums)
        nums = [x - min_ for x in nums]
        max_ -= min_
        n = len(nums)
        # bucket_size = max_+1 / n+1
        n_bucket = n + 1
        buckets = [[] for _ in range(n_bucket)]
        for x in nums:
            bucket_id = (n+1) * x // (max_+1)
            buckets[bucket_id].append(x)
        prev_max = 0
        result = 0
        for bucket in buckets:
            if bucket:
                bucket_min, bucket_max = get_min_max(bucket)
                result = max(result, bucket_min - prev_max)
                prev_max = bucket_max
        return result

for i in range(25):
    import time
    t1 = time.time()
    nums = [random.randint(-10**9, 10**9) for _ in range(2**i)]
    res = Solution().maximumGap(nums)
    t2 = time.time()
    print(i, t2-t1, res)

